530. Биномиальный коэффициент
Сколькими способами можно
выбрать k элементов из n, если не принимать во внимание их
порядок?
Вход. Каждая строка содержит два числа n (n ³ 1) и k (0 £ k £ n). Последняя
строка содержит два ноля и не обрабатывается.
Выход. Для
каждой пары чисел n и k вывести число способов, которыми можно выбрать k элементов из n. Известно, что выводимое
значение всегда меньше 231.
Пример входа
4 2
10 5
49 6
0 0
Пример выхода
6
252
13983816
РЕШЕНИЕ
комбинаторика
Анализ алгоритма
Значение биномиального
коэффициента 
вычислим по формуле:
= 
= 
По условию задачи значение не больше 231 – 1, но в процессе вычислений значения текущих переменных
могут выходить за границы типа int. Поэтому для временных переменных будем
использовать 64-битовый тип long long. Если значение m близко к n, следует
воспользоваться свойством = 
, чтобы не получить Time Limit.
Реализация алгоритма
Функция Cnk(k, n)вычисляет
значение биномиального коэффициента 
.
int Cnk(int
k, int n)
{
long long res = 1;
if (k > n - k) k = n - k;
for(int i = 1; i
<= k; i++)
res = res * (n - i
+ 1) / i;
return (int)res;
}
Основной цикл программы.
Читаем значения n и k и выводим Cnk(k, n).
while(scanf("%d
%d",&n,&k),n + k)
printf("%d\n",Cnk(k,n));